package com.epam.training.collection;

import java.util.Comparator;
import java.util.Iterator;
import java.util.RandomAccess;

public class MyCollections {

	@SuppressWarnings({ "rawtypes", "unchecked" })
	private static int partition(Object arr[], int left, int right) {
		int i = left, j = right;
		Object tmp;
		Comparable pivot = (Comparable) arr[(left + right) >>> 1];
		while (i <= j) {
			while (((Comparable) arr[i]).compareTo(pivot) < 0) {
				i++;
			}

			while (((Comparable) arr[j]).compareTo(pivot) > 0) {
				j--;
			}

			if (i <= j) {
				tmp = arr[i];
				arr[i] = arr[j];
				arr[j] = tmp;
				i++;
				j--;
			}
		}

		return i;
	}

	@SuppressWarnings({ "rawtypes", "unchecked" })
	private static int partition(Object arr[], int left, int right, Comparator c) {
		int i = left, j = right;
		Object tmp;
		Object pivot = arr[(left + right) >>> 1];
		while (i <= j) {
			while (c.compare(arr[i], pivot) < 0) {
				i++;
			}

			while (c.compare(arr[j], pivot) > 0) {
				j--;
			}

			if (i <= j) {
				tmp = arr[i];
				arr[i] = arr[j];
				arr[j] = tmp;
				i++;
				j--;
			}
		}

		return i;
	}

	private static void quickSort(Object arr[], int left, int right) {
		int index = partition(arr, left, right);

		if (left < index - 1) {
			quickSort(arr, left, index - 1);
		}

		if (index < right) {
			quickSort(arr, index, right);
		}
	}

	@SuppressWarnings("rawtypes")
	private static void quickSort(Object arr[], int left, int right,
			Comparator c) {
		int index = partition(arr, left, right, c);

		if (left < index - 1) {
			quickSort(arr, left, index - 1);
		}

		if (index < right) {
			quickSort(arr, index, right);
		}
	}

	@SuppressWarnings({ "unchecked", "rawtypes" })
	private static void bubbleSort(Object array[]) {
		int j;
		boolean flag = true;
		Object temp;

		while (flag) {
			flag = false;
			for (j = 0; j < array.length - 1; j++) {
				if (((Comparable) array[j])
						.compareTo((Comparable) array[j + 1]) > 0) {
					temp = array[j];
					array[j] = array[j + 1];
					array[j + 1] = temp;
					flag = true;
				}
			}
		}
	}

	@SuppressWarnings({ "unchecked", "rawtypes" })
	private static void bubbleSort(Object array[], Comparator c) {
		int j;
		boolean flag = true;
		Object temp;

		while (flag) {
			flag = false;
			for (j = 0; j < array.length - 1; j++) {
				if (c.compare(array[j], array[j + 1]) > 0) {
					temp = array[j];
					array[j] = array[j + 1];
					array[j + 1] = temp;
					flag = true;
				}
			}
		}
	}

	@SuppressWarnings("unchecked")
	public static <T extends Comparable<T>> void sort(MyList<T> list) {
		Object[] array = list.toArray();
		if (list instanceof RandomAccess) {
			quickSort(array, 0, array.length - 1);
		} else {
			bubbleSort(array);
		}

		for (int j = 0; j < array.length; j++) {
			list.set(j, (T) array[j]);
		}
	}

	@SuppressWarnings("unchecked")
	public static <T> void sort(MyList<T> list, Comparator<T> c) {
		Object[] array = list.toArray();
		if (list instanceof RandomAccess) {
			quickSort(array, 0, array.length - 1, c);
		} else {
			bubbleSort(array, c);
		}

		for (int j = 0; j < array.length; j++) {
			list.set(j, (T) array[j]);
		}
	}

	public static <T> void swap(MyList<T> list, int i, int j) {
		final MyList<T> l = list;
		final T tmp = l.get(j);
		l.set(j, l.get(i));
		l.set(i, tmp);
	}

	public static <T> void copy(MyList<T> dest, MyList<T> src) {
		if (src.size() > dest.size()) {
			throw new MyIndexOutOfBoundsException();
		}

		Iterator<T> itr = src.iterator();
		for (int i = 0; i < src.size(); i++) {
			dest.set(i, itr.next());
		}
	}

	public static <T> void reverse(MyList<T> list) {
		int size = list.size();

		Iterator<T> itr = list.iterator();

		MyList<T> tmp = new MyArrayList<T>();

		while (itr.hasNext()) {
			tmp.add(itr.next());
		}

		for (int i = 0; i < size; i++) {
			list.set(i, tmp.remove(size - i - 1));
		}
	}

	public static <T> int binarySearch(
			MyList<? extends Comparable<? super T>> list, T key) {
		if (list instanceof RandomAccess) {
			int low = 0;
			int high = list.size() - 1;

			while (low <= high) {
				int mid = (low + high) >>> 1;
				Comparable<? super T> midVal = list.get(mid);
				int cmp = midVal.compareTo(key);

				if (cmp < 0) {
					low = mid + 1;
				} else if (cmp > 0) {
					high = mid - 1;
				} else {
					return mid;
				}
			}
			return (low + 1);
		}

		return -1;
	}
}
